Largest Number

发表于

Largest Number

Question

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Analysis

  • [10,2] 对于上述用例，虽然10>2,但是显然102<210，所以应该比较的是两个字符串合并后的大小而非单独的字符串数值比较
  • [0,0] 利用Comparator比较后，检查最大的字符是不是以0开头的，假如是直接返回0，否则可能会返回多个0为结果

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    public String largestNumber(int[] nums) {
        if(nums.length==0)  return "";
        String[] str=new String[nums.length];
        for(int i=0;i<nums.length;++i){
            str[i]=String.valueOf(nums[i]);
        }
        
        Comparator<String> cmp=new Comparator<String>(){
            @Override
            public int compare(String a, String b){
                String str1=a+b;
                String str2=b+a;
                return str2.compareTo(str1);    //reverse
            }
        };
        
        Arrays.sort(str,cmp);
        if(str[0].charAt(0)=='0')   return "0";
        StringBuilder res=new StringBuilder();
        for(String tmp:str){
            res.append(tmp);   
        }
        
        return res.toString();
    }
}

Java Comparator 用法

在TreeSet与TreeMap中如何重载Comparator函数

  • Comparator cmp=new Comparator)(){Definition of compare function}

  • 比较函数的返回值往往是int，两个参数 Object a, Object b,假如希望排序结果为正序，即1在2之前，A在B之前等等，返回值为a.compareTo(b)，若希望排序结果为逆序，则返回值为b.compareTo(a)

  • Arrays内第二个参数为自定义的comparator

  • TreeMap与TreeSet则在初始化的时候第一个参数即为comparator，详见链接

    ​